package com.atguigu.algorithm;

public class KMP2 {
    public static void main(String[] args) {

    }
    public static int[] next(String str){
        int[] ret=new int[str.length()];
        ret[0]=-1;
        if(str.length()==1){
            return ret;
        }
        ret[1]=0;
        int j=1;
        int k=ret[j];
        while(j<str.length()-1){
            if(k<0 || str.charAt(j)==str.charAt(k)){
                ret[++j]=++k;
            }else{
                k=ret[k];
            }
        }
        return ret;
    }
    public static int  match(String src,String dest){
        if(src.length()==0 || dest.length()==0){
            return -1;
        }
        if(src.length()>dest.length()){
            return -1;
        }
        int[] next=next(src);
        int i=0;
        int j=0;
        while(i<dest.length()){
            //如果j== -1 或者当前字符串匹配成功，src[j]== dest[i],则 i++ , j++\
            //j=-1,因为next[0] =-1，说明无法匹配，i,j都移位，j从0开始
            if(j==-1|| src.charAt(j)==dest.charAt(i)){
                i++;
                j++;
            }else{
                //字符串匹配失败，j=next[j]
                j=next[j];
            }
            if(j==src.length()){ //匹配成功了
                return i-j;
            }
        }
        return -1;
    }
}
